package com.review.backpack_01;

import java.util.Arrays;

public class BP07 {
    //7. 背包问题求方案数
    //最优解的数量

    public int knapsackProblem(int[] c, int[] v, int V) {
        int[][] dp = new int[c.length + 1][V + 1], key = new int[c.length + 1][V + 1];
        for (int i = 0; i < key.length; i++) {
            Arrays.fill(key[i], 1);    // 初始化为1的目的是保证任何情况下，dp[i][j]总是存在的，存在则至少为1。
        }
        for (int i = 1; i <= c.length; i++) {
            for (int j = V; j > 0; j--) {
                dp[i][j] = dp[i - 1][j];
                key[i][j] = key[i - 1][j];
                if (j >= c[i - 1]) {
                    if (dp[i][j] < dp[i - 1][j - c[i - 1]] + v[i - 1]) {
                        dp[i][j] = dp[i - 1][j - c[i - 1]] + v[i - 1];
                        key[i][j] = key[i - 1][j - c[i - 1]];
                    } else if (dp[i][j] == dp[i - 1][j - c[i - 1]] + v[i - 1]) {
                        key[i][j] += key[i - 1][j - c[i - 1]];
                    }
                }
            }
        }
        System.out.println("最优方案总数： " + key[c.length][V]);
        return dp[c.length][V];
    }

    public static void main(String[] args) {
        System.out.println(new BP07().knapsackProblem(new int[]{1, 3, 4}, new int[]{15, 20, 30}, 4));
    }
}
